package com.unionfind_01;

/**
 * @Author: tgy
 * @Date: 1/12/21 6:15 PM
 *
 * 路径分裂
 *
 *      A
 *      \
 *      B
 *      \
 *      C
 *      \
 *      D
 *      \
 *      E
 *
 *          A
 *         / \
 *        B  C
 *       /    \
 *      D     E
 *
 *    每一个节点都指向它的祖父节点
 *
 */
public class UF_QuickUnion_Rank_PathSpliting extends UF_QuickUnion_Rank {

    public UF_QuickUnion_Rank_PathSpliting(int size) {
        super(size);
    }

    @Override
    public int find(int v) {


        int next;

        while (parents[v] != v) {

            next = parents[v];
            parents[v] = parents[next];
            v = next;
        }

        return v;
    }

    public static void main(String[] args) {

        UF_QuickUnion quickUnion = new UF_QuickUnion_Rank_PathSpliting(9);


        quickUnion.union(1,3);
        quickUnion.union(2,8);
        quickUnion.union(4,7);
        quickUnion.union(3,4);
        quickUnion.union(1,2);


        System.out.println(quickUnion.isSame(1, 4));

    }
}
